package leetcode

import kotlinetc.println

//https://leetcode.com/problems/longest-valid-parentheses/
//类型：动态规划
//todo 目前没有用动态规划做，虽然通过了OJ,待定
fun main(args: Array<String>) {

    //)()())   ")(((((()())()()))()(()))("   ()(()
    ")(((((()())()()))()(()))(".length.println()
    longestValidParentheses("((((()())()()))()(()))").println()

    longestValidParenthesesVersion1("()(()").println()
}

fun longestValidParentheses(s: String): Int {
    var left = 0
    var right = 0
    var i = 0
    var k = 0
    var max = 0
    while (k < s.length) {
        i = k
        left = 0
        right = 0
        var matchCount = 0
        while (left >= right && i < s.length) {
            if (s[i] == '(')
                left++
            if (s[i] == ')') right++

            if (left == right) matchCount = left//保存在遍历过程中已经出现的对数
            i++
        }
        max = Math.max(max, matchCount)
        k++
    }
    return max * 2
}

/**
 * 可以只遍历一遍，在遍历过程中记录左括号和右括号的数量，如果右括号比左括号多，那么右括号数量减一，更新最大对数，
 *遍历一遍似乎只能用动态规划做
 */
@Deprecated("此思路暂时不行")
fun longestValidParenthesesVersion1(s: String): Int {
    var left = 0
    var right = 0
    var i = 0
    var max = 0
    var matchCount = 0
    while (i < s.length) {
        if (s[i] == '(') left++
        if (s[i] == ')') right++

        if (left == right) matchCount = left//保存在遍历过程中已经出现的对数

        if (right > left) {
            left = 0
            right = 0
        }

        max = Math.max(max, matchCount)

        i++
    }

    if (left > right) max = Math.max(max, right)

    return max * 2
}

